#pragma once
#include<iostream>
template <class K>
struct BSTNode
{
    BSTNode<K> *_left;
    BSTNode<K> *_right;
    K _key;

    BSTNode(const K &key) : _key(key), _left(nullptr), _right(nullptr)
    {
    }
};

template <class K>
class BSTree
{
    typedef BSTNode<K> Node;

public:
    BSTree() : _root(nullptr) {}

    bool Insert(const K &key)
    {
        if (_root == nullptr)
        {
            _root = new Node(key);
            return true;
        }
        Node *parent = nullptr;
        Node *cur = _root;
        while (cur)
        {
            if (cur->_key > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                return false;
            }
        }
        cur = new Node(key);
        if (parent->_key < key)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        return true;
    }
    bool Find(const K &key)
    {
        Node *cur = _root;
        while (cur)
        {
            if (cur->_key < key)
            {
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                cur = cur->_left;
            }
            else
            {
                return true;
            }
        }
        return false;
    }
    bool Erase(const K &key)
    {
        Node *parent = nullptr;
        Node *cur = _root;

        while (cur)
        {
            if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else // 找到了
            {
                // 左为空
                if (cur->_left == nullptr)
                {
                    if (cur == _root)
                    {
                        _root = cur->_right;
                    }
                    else
                    {
                        if (parent->_right == cur)
                        {
                            parent->_right = cur->_right;
                        }
                        else
                        {
                            parent->_left = cur->_right;
                        }
                    }
                }
                // 右为空
                else if (cur->_right == nullptr)
                {
                    if (cur == _root)
                    {
                        _root = cur->_left;
                    }
                    else
                    {
                        if (parent->_right == cur)
                        {
                            parent->_right = cur->_left;
                        }
                        else
                        {
                            parent->_left = cur->_left;
                        }
                    }
                }
                else // 左右都不为空
                {
                    Node *parent = cur;
                    Node *leftMax = cur->_left;

                    while (leftMax->_right) // 找到左树的最大节点
                    {
                        parent = leftMax;
                        leftMax = leftMax->_right;
                    }

                    std::swap(cur->_key, leftMax->_key);

                    if (parent->_left == leftMax)
                    {
                        parent->_left = leftMax->_left;
                    }
                    else
                    {
                        parent->_right = leftMax->_left;
                    }

                    cur = leftMax;
                }
                delete cur;
                return true;
            }
        }
        return false;
    }
    void InOrder()
    {
        _InOrder(_root);
        std::cout << std::endl;
    }

    void _InOrder(Node *root)
    {
        if (root == NULL)
        {
            return;
        }

        _InOrder(root->_left);
        std::cout << root->_key << " ";
        _InOrder(root->_right);
    }

private:
    Node *_root;
};